// 题目描述
// 710. 黑名单中的随机数
// 困难
// 232
// 给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。
// 优化你的算法，使它最小化调用语言 内置 随机函数的次数。
// 实现 Solution 类:
// Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数
// int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数
//   示例 1：
// 输入
// ["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
// [[7, [2, 3, 5]], [], [], [], [], [], [], []]
// 输出
// [null, 0, 4, 1, 6, 1, 0, 4]
//
// 解释
// Solution solution = new Solution(7, [2, 3, 5]);
// solution.pick(); // 返回0，任何[0,1,4,6]的整数都可以。注意，对于每一个pick的调用，
//                  // 0、1、4和6的返回概率必须相等(即概率为1/4)。
// solution.pick(); // 返回 4
// solution.pick(); // 返回 1
// solution.pick(); // 返回 6
// solution.pick(); // 返回 1
// solution.pick(); // 返回 0
// solution.pick(); // 返回 4
//   提示:
// 1 <= n <= 109
// 0 <= blacklist.length <= min(105, n - 1)
// 0 <= blacklist[i] < n
// blacklist 中所有值都 不同
//  pick 最多被调用 2 * 104 次
// 通过次数
// 30.9K
// 提交次数
// 70.9K
// 通过率
// 43.5%
// https://leetcode.cn/problems/random-pick-with-blacklist

/**
 * @param {number} n
 * @param {number[]} blacklist
 */
var Solution = function (n, blacklist) {
  // 计算白名单的逻辑边界
  this.sz = n - blacklist.length

  // 创建 map，用于存储白名单“物理位置”和“逻辑位置”的映射
  // 解释：随机选中一个位置 i，
  // 如果 nums[i] 本身是黑名单的数字，
  // 就要把它映射为白名单上的数字
  this.mapping = {}
  for (const b of blacklist) {
    this.mapping[b] = 666
  }

  // last 表示了最后一个数的索引
  let last = n - 1
  for (const b of blacklist) {
    // 如果 b 在区间 [sz, N) 中，随机不到它，可以忽略掉
    if (b >= this.sz) {
      continue
    }

    // this.mapping[last] 判断了映射的位置上放的是不是黑名单中的数字，是则跳过
    while (this.mapping[last]) {
      last--
    }

    // 将实际存储的黑名单数字，映射为逻辑上的白名单数字
    this.mapping[b] = last
    last--
  }
}

/**
 * @return {number}
 */
Solution.prototype.pick = function () {
  let index = Math.floor(Math.random() * this.sz)
  return this.mapping[index] || index
}

const s = new Solution(7, [2, 3, 5])

const set = new Set()
for (let i = 0; i < 100000000; i++) {
  set.add(s.pick())
}
console.log(set)
